package cn.aylog.simpleStack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 计算器底层实现 之
 *  后缀表达式(逆波兰表达式)
 *  计算 (30+4)*5-6 => 30 4 + 5 * 6 -
 */
public class CaculatorDemo3 {
    public static void main(String[] args) {
        PolandCalculator calculator = new PolandCalculator();
        // (30+4)*5-6 => 30 4 + 5 * 6 -
//        String suffixExpression = "30 4 + 5 * 6 -";
//        double res = calculator.polandCalc(suffixExpression);
//        System.out.printf("%s = %f", suffixExpression, res);
//        String expression = "12-5.1+6-7"; // 12 5 - 6 + 7 -
//        String poland = calculator.expressionToPoland(expression);
//        System.out.println("中缀表达式转后缀表达式~");
//        System.out.printf("%s => %s\n" ,expression, poland);
//        double res = calculator.polandCalc(poland);
//        System.out.println("后缀表表达式计算:");
//        System.out.printf("%s = %f", poland, res);
        // 前缀表达式计算
        // 中缀表达式: 1+((2+3)×4)-5 => 前缀表达式: - + 1 * + 2 3 4 5 // 结果 16
//        String prefixExpression = "- + 1 * + 2 3 4 5"; //
//        double res = calculator.calcPrefixPoland(prefixExpression);
//        System.out.println(res);
        String expression = "1+((2+3)*4)-5";
        String prefixPoland = calculator.parseToPrefixPolandExpression(expression);
        System.out.printf("%s = %s\n", expression, prefixPoland);
        double res = calculator.calcPrefixPoland(prefixPoland);
        System.out.printf("%s = %f", expression, res);
    }
}


class PolandCalculator {

    /**
     * 后缀表达式计算
     */
    public double polandCalc(String suffixExpression) {
        List<String> list = polandExpressToList(suffixExpression);
        Stack<Double> numbers = new Stack<>();
        for(String li : list) {
            if(isOperator(li.charAt(0))) {
                double res = _calc(numbers.pop(), numbers.pop(), li.charAt(0));
                numbers.push(res);
            } else {
                numbers.push(Double.parseDouble(li));
            }
        }
        return numbers.pop();
    }

    /**
     * 数值计算
     */
    private double _calc(double num1, double num2, int ch) {
        double ret = 0d;
        switch (ch) {
            case '+':
                ret = num1 + num2;
                break;
            case '-':
                ret = num2 - num1;
                break;
            case '*':
                ret = num1 * num2;
                break;
            case '/':
                ret = num2 / num1;
                break;
        }
        return ret;
    }

    /**
     * 将波兰表达式转换成list数组, 方便遍历
     */
    private List<String> polandExpressToList(String polandExpress) {
        String[] splits = polandExpress.split("[ ]+");
        List<String> retList = new ArrayList<>();
        for(String s : splits) {
            retList.add(s);
        }
        return retList;
    }

    /**
     * 判断当前项是否为操作符
     */
    private boolean isOperator(int ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')';
    }

    /**
     * 获取运算符的优先级
     */
    private int getPriority(int ch) {
        if(ch == '+' || ch == '-') {
            return 1;
        } else if(ch == '*' || ch == '/') {
            return 2;
        } else {
            return 0;
        }
    }

    /**
     * 中缀表达式转后缀表达式
     */
    public String expressionToPoland(String expression) {
        expression = expression.replaceAll("×", "*");
        /*
        步骤(规则):
        1.初始化两个栈:运算符栈s1，储存中间结果的栈s2
        2.从左至右扫描中缀表达式
        3.遇到操作数时，将其压入s2
        4.遇到运算符时，比较其与s1栈顶运算符的优先级
            1).如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
            2).否则，若优先级比栈顶运算符的高，也将运算符压入s1
            3).否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
        5.遇到括号时
            1).如果是左括号“(”，则直接压入s1；
            2).如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
        6.重复步骤2至5，直到表达式的最右边；
        7.将s1中剩余的运算符依次弹出并压入s2；
        8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）
         */
        Stack<Character> s1 = new Stack<>(); // 运算符
        Stack<String> s2 = new Stack<>(); // 结果
        int len = expression.length();
        String temp = "";
        for(int i=0; i<len; ) {
            char ch = expression.charAt(i);
            if(isOperator(ch)) {
                if(s1.isEmpty() || ch == '(') {
                    s1.push(ch);
                } else {
                    if(getPriority(ch) > getPriority(s1.peek())) {
                        s1.push(ch);
                    } else if(ch == ')') {
                        while (true) {
                            char oper = s1.peek();
                            if(oper == '(') {
                                s1.pop();
                                break;
                            } else {
                                s2.push(s1.pop() + "");
                            }
                        }
                    } else {
                        s2.push(s1.pop() + "");
                        continue;
                    }
                }
            } else {
                temp += ch;
                // 操作数,直接入栈
                if((i+1 < len) && isOperator(expression.charAt(i+1)) || (i+1 == len)) {
                    s2.push(temp.trim());
                    temp = "";
                }
            }
            i++;
        }

        while (!s1.isEmpty()) {
            s2.push(s1.pop() + "");
        }
        String retPoland = "";
        while (!s2.isEmpty()){
            retPoland = s2.pop() + " " + retPoland;
        }
        return retPoland;
    }

    /**
     * 中缀表达式转前缀表达式
     */
    public String parseToPrefixPolandExpression(String expression) {
        /*
            步骤(规则):
            1.创建操作栈s1, 临时存储栈s2
            2.从右至左扫描
            3.如果是操作数,直接入s2栈
            4.如果是操作符
                1).如果s1为空,直接入栈, 或者操作符为')', 直接入s1栈
                2).如果当前操作符的优先级大于等于s1的栈顶的操作符, 直接入s1栈,否则s1栈顶操作符压入s2栈,重复4
                3).如果当前操作符为'(',将s1栈顶操作符压入s2,直到遇到'(', 重复4
            5.重复2-4,直到扫描完
            6.将s1中剩余的运算符依次弹出并压入s2
            7.依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式
         */
        Stack<Character> s1 = new Stack<>();
        Stack<String> s2 = new Stack<>();
        String temp = "";
        int len = expression.length();
        for(int i = len-1; i>=0; ) {
            char ch = expression.charAt(i);
            if(isOperator(ch)) {
                if(s1.isEmpty() || ch == ')') {
                    s1.push(ch);
                } else if(ch == '(') {
                    while(s1.peek() != ')') {
                        s2.push(s1.pop() + "");
                    }
                    s1.pop();
                } else if(getPriority(ch) >= getPriority(s1.peek())) {
                    s1.push(ch);
                } else {
                    s2.push(s1.pop() + "");
                    continue;
                }
            } else {
                temp += ch;
                if((i-1 >= 0) && isOperator(expression.charAt(i-1)) || (i == 0)) {
                    s2.push(temp.trim());
                    temp = "";
                }
            }

            i--;
        }
        while (!s1.isEmpty()) {
            s2.push(s1.pop() + "");
        }
        String retPoland = "";
        while (!s2.isEmpty()) {
            retPoland += s2.pop() + " ";
        }
        return retPoland;
    }

    /**
     * 前缀(波兰)表达式求值
     */
    public double calcPrefixPoland(String poland) {
        List<String> list = polandExpressToList(poland);
        /*
         计算过程:
            1.从右至左取值,
            2.遇到操作数,直接入栈,
            3.遇到运算符, 从数栈中取出2个数进行计算
            4.运算结果push到数栈
            5.重复1-4,直到最后
            6.数栈的最后一个数就是结果
         */
        int len = list.size();
        Stack<Double> numbers = new Stack<>();
        for(int i=len-1; i>=0; i--) {
            String item = list.get(i);
            if(item.matches("\\d+")) {
                numbers.push(Double.parseDouble(item));
            } else {
                double num1 = numbers.pop();
                double num2 = numbers.pop();
                double res = _calc(num2, num1, item.charAt(0));
                numbers.push(res);
            }
        }
        return numbers.pop();
    }
}